Algorithmizing the Multiplicity Schwartz-Zippel Lemma

Abstract

The degree maxim states that any non-zero univariate polynomial of degree at most d has at most d roots (counted with multiplicity). A generalization of this to the multivariate setting, proved by Dvir-Kopparty-Saraf-Sudan asserts that over any field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. It has found numerous applications; in particular, in the definition and properties of multiplicity codes by Kopparty-Saraf-Yekhanin.

In this talk, I will describe an algorithmic proof of the MSZ lemma for arbitrary product sets over any field — alternatively, an efficient algorithm for unique decoding of multivariate multiplicity codes from half their minimum distance on arbitrary product sets over all fields. I will first recall the result of Kim and Kopparty who gave an algorithmic version of the SZ lemma (without multiplicities), which our algorithm builds upon. I will also describe an alternate analysis of Forney’s classical generalized minimum distance decoder, which inspires our proof of correctness.